/**
Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
 */
#include "iostream"
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
struct Queue {
  ListNode *front;
  ListNode *rear;
  Queue() {
    front = nullptr;
    rear = nullptr;
  }
  void push(ListNode *node) {
    if (front == nullptr) {
      front = node;
      rear = node;
    } else {
      rear->next = node;
      rear = node;
    }
  }
};
class Solution {
  //   void push(ListNode *top);

public:
  ListNode *mergeTwoLists(ListNode *list1, ListNode *list2) {
    Queue q;
    ListNode *temp1 = list1, *temp2 = list2;
    for (;;) {
      if (!temp1) {
        q.push(temp2);
        return q.front;
      } else if (!temp2) {
        q.push(temp1);
        return q.front;
      } else {
        if (temp1->val < temp2->val) {
          q.push(temp1);
          temp1 = temp1->next;
        } else {
          q.push(temp2);
          temp2 = temp2->next;
        }
      }
    }
  }
};
int main() {
  Solution s;
  ListNode *l1 = new ListNode(1);
  l1->next = new ListNode(2);
  l1->next->next = new ListNode(4);
  ListNode *l2 = new ListNode(1);
  l2->next = new ListNode(3);
  l2->next->next = new ListNode(4);
  ListNode *res = s.mergeTwoLists(l1, l2);
  while (res != nullptr) {
    std::cout << res->val << " ";
    res = res->next;
  }
}